package cn.nawang.ebeim.client.version;

import java.util.*;

/**
 * Given an array of intergers, find two numbers such that they add up to a specific target number.
 * The function twoSum should return indices of the two numbers such that they add up to the target,
 * where index1 must be less than index2 Please note that your returned answers (both index1 and index2) are not zero-based.
 * You may assume that each input would have exactly one solution.
 * Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
 *
 * Created by GanJc on 2016/2/25.
 */
public class TwoSum {

    public static void main(String[] args) {
        int a [] ={2,7,11,15};
        twoSum(a,9);//1,2
        int b [] ={1,2,9,18,25,36,51,74,100};
        twoSum(b,99);//5,8
        int c[] = {3,2,4};
        twoSum(c,6);//2，3

        twoSum2(a,9);//0,1
        twoSum2(b,99);//4,7
        twoSum2(c,6);//1，2

        int d[] = {0,4,3,0};
        twoSum2(d,0);//0,3
    }

    public static void twoSum(int[] numbers,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            map.put(numbers[i],i+1);//最关键一句,值做key,下标做value,省去查询时的遍历
        }
        for (int i = 0; i < numbers.length; i++) {
            int a = numbers[i];
            int b = target - a ;
            if(map.containsKey(b)){
                int index1 =map.get(a) ;
                int index2 =map.get(b) ;
                System.out.println("index1="+index1+" , index2="+index2);
                break;
            }
        }
    }

    //输入数组有重复的情况下的解,
    public static int[] twoSum2(int[] nums, int target) {
        int ans[] =new int[2];
        List<Integer> list = new ArrayList<>();
        for (int i : nums) {
            list.add(i);
        }
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            int b = target - a ;
            if(list.contains(b)){
                int bi = list.lastIndexOf(b) ;
                if(bi==i){
                    continue;
                }
                ans[0] = i ;
                ans[1] = bi;
                System.out.println("index1="+ans[0]+" , index2="+ans[1]);
                break;
            }
        }
        return ans ;
    }
}
